1. Field of the Invention
The present invention relates to a method for implementing the RSA encoding procedure or a derived procedure by means of a microcontroller, which method involves performing a modulo-N exponentiation by e of a message M; N, e and M being integers of a large length contained in an n-bit format, according to which method the calculation of the modulo-N exponentiation is broken down into two successive operations, of which the first operation has the form: EQU B.sub.i =a.sub.i.X+T.2.sup.m
where B.sub.i and X are calculation variables which depend on M and N, where a.sub.i is an extract of a format restricted to m bits of a calculation variable A whose value results from a previous operation, which extract is taken in the decreasing order of weight of A, of rank i, and where T is a summing variable used for the calculation of the variable A, and the second operation consists of reducing the length of the variable B.sub.i by subtracting a predetermined multiple of the modulus N, and of obtaining a new value A.sub.i for the variable A.
The present invention also relates to an arrangement implementing a method of this type.
2. Description of the Related Art
The encoding procedure termed RSA, after the names of its inventors, is specifically known from U.S. Pat. No. 4,405,829. The advantages of this procedure, especially the fact that it is of the "public key" type, are also widely known. Its implementation by means of powerful processors which have sufficiently large memories to store numbers of great lengths, does not pose any particular problems. It is different when one seeks to employ the same method by means of very small systems, and particularly by means of integrated semiconductor circuits of the microcontroller type which can be incorporated in a portable card termed smart card or also chip card. Given the fact that numerous possible and useful applications are foreseen for this type of system in the private transmission domain (authentication of a speaker, signature, exchange of keys, exchange of confidential information, electronic money etc.) considerable research has actually been made in this domain. It is an object of this research to obtain a system and means for implementing the encoding method RSA which would succeed in accomplishing data processing in a reasonable length of time (a second at the most), despite the serious restrictions imposed by the use of an integrated circuit realised according to current technologies.
With respect to the technological limitations of the current arrangements one may bring forward the small memory capacity (several hundred bytes), the low clock rate (only of the order of 8 MHz) and the small number of bits processed in parallel (8 or 16 bits only).
A system according to the introductory paragraph for implementing the RSA encoding procedure by means of a microcontroller, has been described in French Patent Specification FR-A 2 613 861.
The processing algorithm described avoids making calculations on very large numbers and for this purpose uses a fraction of the calculation variables and a modulo-N reduction after each partial multiplication, so as to avoid these variables becoming longer according as an operation is performed sequentially.
A considerable drawback of the prior-art system resides in the fact that at each modulo-N reduction stage a sign test is necessary, which determines whether the subtraction of the multiple of N has been excessive, in which case an addition by N will be performed to assign again a positive value to the calculation variable A. For that matter, such a drawback is not restricted to the case of the algorithm known from the aforementioned document, but occurs generally in the current state of the art.
Whereas the calculation operations may be performed at high speed by a special calculation element, connected in parallel to a central program management unit, operations for testing the sign can only be carried out by the central unit, and the operation of the element is thus to be interrupted while the result of the test is being awaited.
The slowing down of the processing due to the test operations in question is all the more significant as it has to occur for a large number of times during the modulo-N exponentiation, and as the operation cycle time of the central unit is comparatively slow with respect to the operation cycle time of the calculation element, typically at a ratio of 8 to 1.